#include "search_binary_tree.h"

void K_test_sb_tree1()
{
    key::sb_tree<int> sb_t;

   int arr[] = {9,2,4,6,7,1,3,6,4,1,5,2};

   for(int e : arr)
   {
       sb_t.insert(e);
   }

   sb_t.in_order();

   key::sb_tree<int>::node* ret = sb_t.find(2);

   cout << ret->_key << endl;
}

void K_test_sb_tree2() 
{
    key::sb_tree<int> sb_t;

    int arr[] = {-1,-2,-3,0,8,6,5,4,7,1,2,3};

    for (int e : arr)
    {
        sb_t.insert(e);
    }

    sb_t.in_order();
    
    sb_t.erase(-1);
    sb_t.in_order();

    sb_t.erase(6);
    sb_t.in_order();

    sb_t.erase(-3);
    sb_t.in_order();

    sb_t.erase(4);
    sb_t.in_order();

    sb_t.erase(3);
    sb_t.in_order();

    sb_t.erase(7);
    sb_t.in_order();

    sb_t.erase(-2);
    sb_t.in_order();

    sb_t.erase(8);
    sb_t.in_order();

    sb_t.erase(5);
    sb_t.in_order();

    sb_t.erase(0);
    sb_t.in_order();

    sb_t.erase(2);
    sb_t.in_order();

    sb_t.erase(1);
    sb_t.in_order();
}

void K_test_sb_tree_recursive1()
{
    key::sb_tree<int> sb_t;

   int arr[] = {9,2,4,6,7,1,3,6,4,1,5,2};

   for(int e : arr)
   {
       sb_t.insert_recursive(e);
   }

   sb_t.in_order();

   key::sb_tree<int>::node* ret = sb_t.find_recursive(6);

   cout << ret->_key << endl;

}

void K_test_sb_tree_recursive2()
{
    key::sb_tree<int> sb_t;

    int arr[] = {-1,-2,-3,0,8,6,5,4,7,1,2,3};

    for (int e : arr)
    {
        sb_t.insert(e);
    }

    sb_t.in_order();
    
    sb_t.erase_recursive(-1);
    sb_t.in_order();

    sb_t.erase_recursive(6);
    sb_t.in_order();

    sb_t.erase_recursive(-3);
    sb_t.in_order();

    sb_t.erase_recursive(4);
    sb_t.in_order();

    sb_t.erase_recursive(3);
    sb_t.in_order();

    sb_t.erase_recursive(7);
    sb_t.in_order();

    sb_t.erase_recursive(-2);
    sb_t.in_order();

    sb_t.erase_recursive(8);
    sb_t.in_order();

    sb_t.erase_recursive(5);
    sb_t.in_order();

    sb_t.erase_recursive(0);
    sb_t.in_order();

    sb_t.erase_recursive(2);
    sb_t.in_order();

    sb_t.erase_recursive(1);
    sb_t.in_order();
}

void KV_test_sb_tree1()
{
    //字典KV模型
    key_value::sb_tree<string, vector<string>> dict;
    dict.insert("sort", {"排序"});
    dict.insert("left", {"左边"});
    dict.insert("right", {"右边"});
    dict.insert("map", {"地图", "、映射"});

    string str;
    while(cin >> str)
    {
        key_value::sb_tree<string, vector<string>>::node* ret = dict.find(str);
        if (ret)
        {
            cout << "找到了这个单词,对应的中文解释是:" ;
            vector<string>::iterator it = (ret->_value).begin();
            while(it != (ret->_value).end())
            {
                cout << (*it);
                it++;
            }
            cout << endl;
        }
        else 
        {
            cout << "没有这个单词!" << endl;
        }
    }
}

void KV_test_sb_tree_recursive1()
{
    //字典KV模型
    key_value::sb_tree<string, vector<string>> dict;
    dict.insert_recursive("sort", {"排序"});
    dict.insert_recursive("left", {"左边"});
    dict.insert_recursive("right", {"右边"});
    dict.insert_recursive("map", {"地图", "、映射"});

    string str;
    while(cin >> str)
    {
        key_value::sb_tree<string, vector<string>>::node* ret = dict.find(str);
        if (ret)
        {
            cout << "找到了这个单词,对应的中文解释是:" ;
            vector<string>::iterator it = (ret->_value).begin();
            while(it != (ret->_value).end())
            {
                cout << (*it);
                it++;
            }
            cout << endl;
        }
        else 
        {
            cout << "没有这个单词!" << endl;
        }
    }
}
void KV_test_sb_tree2()
{
    string arr[] = { "苹果", "西瓜","草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

    key_value::sb_tree<string, int> count_tree;
    for (string str : arr)
    {
        key_value::sb_tree<string, int>::node* ret = count_tree.find(str);
        if (ret)
        {
            ret->_value++;
        }
        else 
        {
            count_tree.insert(str, 1);
        }
    }

    count_tree.in_order();
}

void KV_test_sb_tree_recursive2()
{
    string arr[] = { "苹果", "西瓜","草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

    key_value::sb_tree<string, int> count_tree;
    for (string str : arr)
    {
        key_value::sb_tree<string, int>::node* ret = count_tree.find(str);
        if (ret)
        {
            ret->_value++;
        }
        else 
        {
            count_tree.insert_recursive(str, 1);
        }
    }

    count_tree.in_order();

}

int main()
{
    //K_test_sb_tree1(); 
    //K_test_sb_tree2(); 
    //K_test_sb_tree_recursive1(); 
    //K_test_sb_tree_recursive2(); 
    
    //KV_test_sb_tree1();
    //KV_test_sb_tree_recursive1();
    //KV_test_sb_tree2();
    KV_test_sb_tree_recursive2();
    return 0;
}
